package 数组;

public class L41 {

    public static void main(String[] args) {
        int[] nums = new int[]{7,8,9,11,12};
        System.out.println(new L41().firstMissingPositive(nums));
    }

    public int firstMissingPositive(int[] nums) {

        int size = nums.length;
        // 把小于0的数置为 n+1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = size + 1;
            }
        }

        // 把在0～n中的数对应的位置变为负数
        for (int i = 0; i < nums.length; i++) {
            int n = Math.abs(nums[i]);
            if (n <= nums.length) {
                nums[n - 1] = -Math.abs(nums[n - 1]);
            }
        }

        // 遍历获取第一个正数的下标
        for (int i = 0; i < nums.length; ++i) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }
        return size + 1;

    }
}
